|
The #P-completeness of 01-permanent, sometimes known as Valiant's theorem,〔Christos H. Papadimitriou. ''Computational Complexity.'' Addison-Wesley, 1994. ISBN 0-201-53082-1. Page 443〕 is a mathematical proof about the permanent of matrices, considered a seminal result in computational complexity theory.〔Allen Kent, James G. Williams, Rosalind Kent and Carolyn M. Hall (editors). (''Encyclopedia of microcomputers''. )Marcel Dekker, 1999. ISBN 978-0-8247-2722-2; p. 34〕〔Jin-Yi Cai, A. Pavan and D. Sivakumar, (''On the Hardness of Permanent.'' ) In: STACS, '99: 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4–6, 1999 Proceedings. pp. 90–99. Springer-Verlag, New York, LLC Pub. Date: October 2007. ISBN 978-3-540-65691-3; p. 90.〕 In a 1979 scholarly paper, Leslie Valiant proved that the computational problem of computing the permanent of a matrix is #P-hard, even if the matrix is restricted to have entries that are all 0 or 1. In this restricted case, computing the permanent is even #P-complete, because it corresponds to the #P problem of counting the number of permutation matrices one can get by changing ones into zeroes. Valiant's 1979 paper also introduced #P as a complexity class.〔Lance Fortnow. (''My Favorite Ten Complexity Theorems of the Past Decade.'' ) Foundations of Software Technology and Theoretical Computer Science: Proceedings of the 14th Conference, Madras, India, December 15–17, 1994. P. S. Thiagarajan (editor), pp. 256–275, Springer-Verlag, New York, 2007. ISBN 978-3-540-58715-6; p. 265〕 ==Significance== One reason for interest in the computational complexity of the permanent is that it provides an example of a problem where constructing a single solution can be done efficiently but where counting all solutions is hard. As Papadimitriou writes in his book ''Computational Complexity'': Specifically, computing the permanent (shown to be difficult by Valiant's results) is closely connected with finding a perfect matching in a bipartite graph, which is solvable in polynomial time by the Hopcroft–Karp algorithm.〔John E. Hopcroft, Richard M. Karp: ''An Algorithm for Maximum Matchings in Bipartite Graphs.'' SIAM J. Comput. 2(4), 225–231 (1973)〕 For a bipartite graph with ''2n'' vertices partitioned into two parts with ''n'' vertices each, the number of perfect matchings equals the permanent of its biadjacency matrix and the square of the number of perfect matchings is equal to the permanent of its adjacency matrix.〔 Since any 0–1 matrix is the biadjacency matrix of some bipartite graph, Valiant's theorem implies〔Dexter Kozen. (''The Design and Analysis of Algorithms.'' ) Springer-Verlag, New York, 1991. ISBN 978-0-387-97687-7; pp. 141–142〕 that the problem of counting the number of perfect matchings in a bipartite graph is #P-complete, and in conjunction with Toda's theorem this implies that it is hard for the entire polynomial hierarchy.〔Seinosuke Toda. (PP is as Hard as the Polynomial-Time Hierarchy. ) SIAM Journal on Computing, Volume 20 (1991), Issue 5, pp. 865–877.〕〔(1998 Gödel Prize. Seinosuke Toda )〕 The computational complexity of the permanent also has some significance in other aspects of complexity theory: it is not known whether NC equals P (informally, whether every polynomially-solvable problem can be solved by a polylogarithmic-time parallel algorithm) and Ketan Mulmuley has suggested an approach to resolving this question that relies on writing the permanent as the determinant of a matrix.〔Ketan Mulmuley. (Lower Bounds in a Parallel Model without Bit Operations. ) SIAM Journal on Computing, Volume 28 (1999), Issue 4, pp. 1460–1509.〕 Hartmann 〔W. Hartmann. (On the complexity of immanants. ) Linear and Multilinear Algebra 18 (1985), no. 2, pp. 127–140.〕 proved a generalization of Valiant's theorem concerning the complexity of computing immanants of matrices that generalize both the determinant and the permanent. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sharp-P-completeness of 01-permanent」の詳細全文を読む スポンサード リンク
|